package com.zang.backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.function.Function;
import java.util.function.Predicate;

/**
 * @author ZVerify
 * @since 2022/11/13 14:35
 * @see <a href="https://leetcode.cn/problems/palindrome-partitioning/">...</a>
 **/
public class 分割回文串 {

    // 返回数据
    List<List<String>> result = new ArrayList<>();
    // 中间数据
    List<String> list = new ArrayList<>();
    public List<List<String>> partition(String s) {

        backtrack(s,0);
        return result;
    }

    private void backtrack(String str, int startIndex) {
            if (startIndex == str.length()) {
                result.add(new ArrayList<>(list));
            }

            for (int i = startIndex; i < str.length(); i++) {
                if ( !isCancel(str,startIndex,i) ) {
                    continue;
                }
                list.add(str.substring(startIndex,i));
                backtrack(str,i+1);
                list.remove(list.size() - 1);
            }

    }

    boolean isCancel(String str, int startIndex, int endIndex) {

        while (startIndex < endIndex) {
            if (str.charAt(startIndex) != str.charAt(endIndex)) {
                return false;
            }
            startIndex++;endIndex--;
        }
        return true;
    }
}
